package mo.tags.stack;

import java.util.Stack;

public class L946 {

    public boolean validateStackSequences(int[] pushed, int[] popped) {
        Stack<Integer> stack = new Stack<>();
        int n = pushed.length;
        int pushI = 0, popJ = 0;
        while (pushI < n) {
            if (pushed[pushI] != popped[popJ]) {
                stack.push(pushed[pushI]);
            } else {
                popJ++;
                while (!stack.isEmpty() && stack.peek() == popped[popJ]) {
                    stack.pop();
                    popJ++;
                }
            }
            pushI++;
        }
        while (!stack.isEmpty() && popJ < n) {
            if (stack.pop() != popped[popJ]) {
                return false;
            }
            popJ++;
        }
        return popJ == n;
    }


    public static void main(String[] args) {
        L946 test = new L946();
        int[] pushed = new int[]{2, 1, 0};
        int[] popped = new int[]{1, 2, 0};
        System.out.println(test.validateStackSequences(pushed, popped));
    }

}
